//
//  Problem977.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/4/13.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 977. 有序数组的平方
 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

 示例 1：
     输入：nums = [-4,-1,0,3,10]
     输出：[0,1,9,16,100]
     解释：平方后，数组变为 [16,1,0,9,100]
     排序后，数组变为 [0,1,9,16,100]
 示例 2：
     输入：nums = [-7,-3,2,3,11]
     输出：[4,9,9,49,121]
 提示：
     1 <= nums.length <= 104
     -104 <= nums[i] <= 104
     nums 已按 非递减顺序 排序
 进阶：
    请你设计时间复杂度为 O(n) 的算法解决本问题
 */
@objcMembers class Problem977: NSObject {
    func solution() {
        print(sortedSquares([1]))
        print(sortedSquares([-1]))
        print(sortedSquares([-3, 2]))
        print(sortedSquares([-4,-1,0,3,10]))
        print(sortedSquares([-7,-3,2,3,11]))
    }
    
    /*
     1: 创建2个指针left、right，分别指向数组的0和n-1的位置
     2: 比较 nums[left]*nums[left] 和 nums[right]*nums[right] 的大小，把大的插入数组的0的位置
     3: 假如 left > right : left += 1;  否则 right -=1
     */
    func sortedSquares(_ nums: [Int]) -> [Int] {
        if nums.count == 1 {
            return [nums[0] * nums[0]]
        }
        var left = 0
        var right = nums.count-1
        var leftValue = -1
        var rightValue = -1
        var list:[Int] = []
        while left < right {
            if leftValue == -1 {
                leftValue = nums[left] * nums[left]
            }
            if rightValue == -1  {
                rightValue = nums[right] * nums[right]
            }
            
            if leftValue > rightValue {
                list.insert(leftValue, at: 0)
                leftValue = -1
                left += 1
            } else {
                list.insert(rightValue, at: 0)
                rightValue = -1
                right -= 1
            }
        }
        if leftValue >= 0 {
            list.insert(leftValue, at: 0)
        }
        if rightValue >= 0 {
            list.insert(rightValue, at: 0)
        }
        
        
        return list
    }
}
